package main.leetcode.offer.firstround.from51to68;

import java.util.Arrays;

/**
 * 56-I.数组中数字出现的次数
 *
 * <p>一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 *
 * <p>
 *
 * <p>示例 1：输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]
 *
 * <p>示例 2：输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
 *
 * <p>限制：2 <= nums <= 10000
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex56I {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(new ex56I().singleNumbers(new int[] {3, 0, 1, 0, 2, 3})));
    }
    // HashMap
    //    public int[] singleNumbers(int[] nums) {
    //        if (nums.length == 2) return nums;
    //        HashMap<Integer, Integer> map = new HashMap<>();
    //        for (int val : nums) {
    //            if (map.containsKey(val)) map.put(val, 2);
    //            else map.put(val, 1);
    //        }
    //        int[] res = {Integer.MAX_VALUE, Integer.MAX_VALUE};
    //        for (int val : map.keySet()) {
    //            if (map.get(val) == 1) {
    //                if (res[0] == Integer.MAX_VALUE) res[0] = val;
    //                else {
    //                    res[1] = val;
    //                    break;
    //                }
    //            }
    //        }
    //        return res;
    //    }
    public int[] singleNumbers(int[] nums) {
        int x = 0;
        // 得到唯一的两个数的异或结果——基于 异或的可交换性/任何数与0异或结果都是本身/任何数与自身异或结果都为0
        /** 得到A^B的结果 基于异或运算的以下几个性质 1. 交换律 2. 结合律 3.对于任何数x，都有x^x=0，x^0=x */
        for (int val : nums) x ^= val;

        int flag = x & (-x); // x & (-x)本身的作用是得到最低位的1，而我们所需要的做到的是：利用这个1进行分组
        // 前面已经知道，x是我们需要的结果数A和B相异或的结果，也就是说，x的二进制串上的任何一个1，都能成为区分A和B的条件
        // 因此我们只需要得到x上的任意一个1，就可以做到将A和B区分开来
        int res = 0;
        // 1  0001  第一组
        // 2  0010  第二组
        // 1  0001  第一组
        // 3  0011  第二组
        // 2  0010  第二组
        // 5  0101  第一组
        // 第一组 1 1 5  第二组 2 3 2
        for (int val : nums) {
            // 分组，由于异或运算具有可逆性质，因此只需得到其中一个数即可
            if ((flag & val) != 0) {
                res ^= val;
                System.out.println(res);
            }
        }
        // 利用先前的x进行异或运算得到另一个
        return new int[] {res, x ^ res};
    }
}
